package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         113,
		Discription: "从根节点到叶子节点的元素和为指定值的所有路径",
		Level:       2,
		Labels: map[string]int{
			"递归	":  1,
			"二叉树": 1,
		},
	})
}

func PathSum(root *ds.TreeNode, targetSum int) [][]int {
	res := make([][]int, 0)
	path := make([]int, 0)
	var travel func(*ds.TreeNode, int)
	travel = func(node *ds.TreeNode, sum int) {
		if node == nil {
			return
		}

		sum += node.Val
		path = append(path, node.Val)
		//保证方法结束返回上一个方法时，path的值没有被修改
		defer func() {
			path = path[:len(path)-1]
		}()

		if sum == targetSum {
			if node.Left == nil && node.Right == nil {
				res = append(res, append([]int(nil), path...))
				return
			}
		}

		travel(node.Left, sum)
		travel(node.Right, sum)
	}

	travel(root, 0)
	return res
}
